package com.leetcode.根据数据结构分类.二叉树;

import java.util.ArrayDeque;

/**
 * @author: ZhouBert
 * @date: 2021/3/12
 * @description: 331. 验证二叉树的前序序列化
 * https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/
 * 卧槽木有思路
 * 这是一个判断二叉树的问题！
 */
public class B_331_验证二叉树的前序序列化 {

	static B_331_验证二叉树的前序序列化 action = new B_331_验证二叉树的前序序列化();

	public static void main(String[] args) {
		test1();
	}

	public static void test1() {
		String preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#";
		boolean res = action.isValidSerialization(preorder);
		System.out.println("res = " + res);
	}

	/**
	 * 这个题目感觉似乎只要保证：
	 * 1.节点的大小需要满足 奇数（不一定是满二叉树）
	 * 2.根节点不能是 空 ->
	 * 3.叶子节点必须为空
	 * --
	 * 好吧必须承认，这道题我想不出来！
	 * 题解是通过栈的方式实现的：
	 * 核心思路：遇到 x##,转化为 #
	 *
	 * @param preorder
	 * @return
	 */
	public boolean isValidSerialization(String preorder) {
		String[] strs = preorder.split(",");
		int len = strs.length;
		if ((len & 1) == 0) {
			return false;
		}
		//接下来就需要判断根节点和叶子节点的规律了
		ArrayDeque<String> deque = new ArrayDeque<>(len);
		deque.addLast(strs[0]);
		for (int i = 1; i < len; i++) {
			if ("#".equals(strs[i]) && "#".equals(deque.peekLast())) {
				do {
					if (deque.size() < 2) {
						return false;
					}
					deque.removeLast();
					deque.removeLast();
				} while (!deque.isEmpty() && "#".equals(deque.peekLast()));
			}
			deque.addLast(strs[i]);

		}
		return deque.size() == 1 && "#".equals(deque.peekFirst());
	}


}
